from threading import Lock


class ArrayQueueItem:
    def __init__(self):
        self.back = None
        self.front = None
        self.value = None
        self.index = 0


class ArrayQueue:
    def __init__(self):
        self.first = None
        self.last = None
        self.count = 0
        self.index = 0
        self.index_collect = {}
        self.lock = Lock()

    def empty(self):
        return self.first is None

    def clear(self):
        self.lock.acquire()
        self.first = None
        self.last = None
        self.count = 0
        self.index = 0
        self.index_collect = {}
        self.lock.release()

    def put(self, item, add_index=False):
        self.lock.acquire()
        val_item = ArrayQueueItem()
        val_item.index = self.index
        val_item.value = item
        val_item.front = self.last
        self.index += 1
        if self.empty():
            self.first = val_item
        else:
            self.last.back = val_item
        self.last = val_item
        if add_index:
            self.index_collect[val_item.index] = val_item
        self.count += 1
        self.lock.release()
        return val_item

    def add_index(self, array_queue_item):
        self.index_collect[array_queue_item.index] = array_queue_item

    def get_index(self, index=None):
        queue_item = self.read_item(index)
        front = queue_item.front
        back = queue_item.back
        if front is None:
            self.first = back
        else:
            front.back = back
        if back is None:
            self.last = front
        else:
            back.front = front
        if queue_item.index in self.index_collect.items():
            del self.index_collect[queue_item.index]
        return queue_item.val

    def get(self):
        self.lock.acquire()
        if self.first is None:
            return None
        queue_item = self.first
        self.first = queue_item.back
        val = queue_item.value
        if queue_item.index in self.index_collect.items():
            del self.index_collect[queue_item.index]
        self.count -= 1
        if self.count > 0:
            self.first.front = None
            self.last.back = None
        else:
            self.first = None
            self.last = None
        self.lock.release()
        return val

    def last_index(self):
        return self.index

    def set_value(self, index, value):
        val_item = self.read_item(index)
        if val_item is not None:
            val_item.value = value

    def contains(self, index):
        if index in self.index_collect:
            return True
        queue_item = self.first
        while queue_item is not None:
            if queue_item.index == index:
                return True
            queue_item = queue_item.back
        return False

    def read_item(self, index=None):
        if index is None:
            return self.first
        elif index in self.index_collect:
            return self.index_collect[index]
        queue_item = self.first
        while queue_item is not None:
            if queue_item.index == index:
                return queue_item
            queue_item = queue_item.back
        return None

    def read(self, index=None):
        read_val = self.read_item(index)
        if read_val is None:
            return None
        return read_val.value




